package com.ww.springboot.boot.algorithm.dp;

/**
 * 描述：积雨图
 *
 * 计算出每个坐标 左最高点和右最高点 取较小值 即可算出积雨面积
 *
 * 已知i-1最高点 只需要跟i比较 即可得到i的最高点  --此逻辑包含动态规划思想
 *
 * @author wanwei
 * @since 2021-08-21 16:50
 */
public class JiYuTuDemo {

    public static void main(String[] args) {

        int[] array = {4,2,0,3,2,5};
        System.out.println(trap(array));
    }

    public static int trap(int[] height) {
        if (height == null || height.length<3)
            return 0;
        int ret = 0;
        int len = height.length;
        int[] leftMax = new int[len];   // i下标及其左边最高的元素
        int[] rightMax = new int[len];  // i下标及其右边最高的元素
        // 初始化leftMax
        leftMax[0] = height[0];
        for (int i=1; i<len; i++) {
            leftMax[i] = Math.max(leftMax[i-1], height[i]);
        }
        // 初始化rightMax
        rightMax[len -1] = height[len - 1];
        for (int i=len-2; i>-1; i--) {
            rightMax[i] = Math.max(rightMax[i+1], height[i]);
        }
        // 计算面积
        for (int i=0; i<len; i++) {
            ret += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ret;
    }
}
